package one.stack;

import java.util.Stack;

/**
 * 逆波兰表达式求值
 */
public class EvalRPN {
    //思路：1）使用栈，存操作数。2）遇到算数运算符，要先比较优先级。3）运算
    //时间复杂度：O(n)
    public static int evalRPN(String[] tokens) {

        Stack numsStack = new Stack<>();
        for(String token : tokens){
            if(token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")){//是运算符，取出栈顶两个操作数，运算结果入栈
                int b = (int)numsStack.pop();
                int a = (int)numsStack.pop();
                numsStack.push(calc(a, b, token));//注意点：不要忘记将运算结果入栈
            }else{//操作数入栈
                numsStack.push(Integer.parseInt(token));
            }
        }
        return (int)numsStack.pop();
    }
    private static int calc(int a, int b, String op){
        if(op.equals("+")) return a + b;
        if(op.equals("-")) return a - b;
        if(op.equals("*")) return a * b;
        if(op.equals("/")) return a / b;
        return 0;
    }

    public static void main(String[] args) {
        int result = evalRPN(new String[]{"10","6","9","3","+","-11","*","/","*","17","+","5","+"});
        System.out.println(result);
    }
}
